/* Universidad del Valle de Guatemala
 * CC2003 - Algoritmos y Estructuras de Datos
 * HOJA DE TRABAJO #5.2
 * Fecha de Entrega: Jueves 22 de Septiembre de 2011
 */

/**
 * Clase que define las acciones que puede realizar la Cola implementada por medio de una Priority Queue. 
 * @author José Antonio Bagur - 10275
 */

public class PriorityQueueBanco <E> extends AbstractQueue <E> {
    
    /* ATRIBUTOS DE LA CLASE PRIORITYQUEUEBANCO */
    
    public E[] datos;
    private int tamaño;
    
    /**
     * Constructor de la Clase PriorityQueueBanco, inicializa los atributos de la cola. 
     * @param capacidad de almacenamiento de la cola.
     */
    public PriorityQueueBanco(int capacidad) {
        datos = (E[]) new Object[capacidad];
        tamaño = 0;
    }
    
    /**
     * Método que permite ingresar valores determinados a la PriorityQueue.
     * @param valor ingresado a la cola.
     * @throws QueueOverflow 
     */
    public void add(E valor) throws QueueOverflow {
        int pos = tamaño;                                                       // POSICIÓN VIRTUAL  DEL VALOR INGRESADO
        int pPos = ((pos - 1)/2);                                               // POSICIÓN DEL PADRE
        tamaño++;
        Comparable<E> valorComparacion = (Comparable<E>) valor;
        
        while (pos > 0 && valorComparacion.compareTo(datos[pPos]) < 0) {
            datos[pos] = datos[pPos];                                           // MOVER PADRE A POSICIÓN.
            pos = pPos;                                                         // MOVER HACIA ARRIBA.
            pPos = ((pos - 1)/2);
        }
        
        datos[pos] = valor;                                                     // POSICIÓN FINAL DEL VALOR INGRESADO
        this.contador++;
    }
    
    /**
     * Método que permite extraer el primer elemento de la PriorityQueue.
     * @return ret primer elemento de la cola.
     * @throws QueueUnderflow 
     */
    public E remove() throws QueueUnderflow {
        E ret = datos[0];
        tamaño--;                                                               // MOVER ÚLTIMO ELEMENTO A LA RAIZ.            
        Comparable <E> toTrickle = (Comparable <E>) datos[tamaño];              // MOVER HACIA ABAJO.
        datos[tamaño] = null;
        int pos = 0;
        while(true) {
            int menor = ((2 * pos) + 1);                                        // DETERMINAR HIJO MENOR.
            
            if (menor >= tamaño)
                break;
            
            Comparable <E> izquierda = (Comparable <E>) datos[menor];
            
            if (menor + 1 < tamaño && izquierda.compareTo(datos[menor + 1]) > 0) {
                menor++;
            }
            
            if(toTrickle.compareTo(datos[menor]) < 0)
                break;
            
            datos[pos] = datos[menor];
            pos = menor;
        }
        
        datos[pos] = (E) toTrickle;
        this.contador--;
        return ret;
    }
    
    /**
     * Método que retorna el primer elemento de la PriorityQueue, sin retirarlo de ésta.
     * @return primer elemento de la cola.
     * @throws QueueUnderflow 
     */
    public E peek() throws QueueUnderflow {
        return datos[0];
    }  

} // FIN DE LA CLASE PRIORITYQUEUEBANCO

